#include "main/utils.h"
#include "lib/list.h"
using namespace std;

class Solution {
  public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
      int lena = 0, lenb = 0;
      auto head = headA;
      while (head) {
        ++lena;
        head = head->next;
      }
      head = headB;
      while (head) {
        ++lenb;
        head = head->next;
      }
      auto heada = headA;
      auto headb = headB;
      if (lena > lenb) {
        for (int i = 0; i < lena - lenb; ++i) {
          heada = heada->next;
        }
      } else if (lenb > lena) {
        for (int i = 0; i < lenb - lena; ++i) {
          headb = headb->next;
        }
      }
      while (heada != headb) {
        heada = heada->next;
        headb = headb->next;
      }
      return heada;
    }

    ListNode *getIntersectionNode1(ListNode *headA, ListNode *headB) {
      unordered_set<ListNode*> st;
      auto head = headA;
      while (head) {
        st.insert(head);
        head = head->next;
      }
      head = headB;
      while (head) {
        if (st.count(head)) {
          return head;
        }
        head = head->next;
      }
      return nullptr;
    }

    ListNode *getIntersectionNode2(ListNode *headA, ListNode *headB) {
      if (!headA || !headB) {
        return nullptr;
      }
      auto pa = headA, pb = headB;
      while (pa != pb) {
        pa = (pa == nullptr) ? headB : pa->next;
        pb = (pb == nullptr) ? headA : pb->next;
      }
      return pa;
    }
};

int main() {
  ListNode* p1 = new ListNode();
  p1->value = 4;
  ListNode* p2 = new ListNode();
  p2->value = 1;
  ListNode* p3 = new ListNode();
  p3->value = 8;
  ListNode* p4 = new ListNode();
  p4->value = 4;
  ListNode* p5 = new ListNode();
  p5->value = 5;
  ListNode* p6 = new ListNode();
  p6->value = 5;
  ListNode* p7 = new ListNode();
  p7->value = 6;
  ListNode* p8 = new ListNode();
  p8->value = 1;

  ConnectNode(p1, p2);
  ConnectNode(p2, p3);
  ConnectNode(p3, p4);
  ConnectNode(p4, p5);
  ConnectNode(p6, p7);
  ConnectNode(p7, p8);
  ConnectNode(p8, p3);

  Solution su;
  auto output = su.getIntersectionNode(p1, p6);
  cout << output->value << endl;
  auto output1 = su.getIntersectionNode1(p1, p6);
  cout << output1->value << endl;
  auto output2 = su.getIntersectionNode2(p1, p6);
  cout << output2->value << endl;
}
